/**
 * describe:
 *
 * @author chaP
 * @date 2018/12/18
 */
/**题目描述： 把只包含质因子2、3和5的数称作丑数（Ugly Number）。
 *          例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
 *          求按从小到大的顺序的第N个丑数
 他人思路：丑数一定是p=2^x*3^y*5^z,即丑数必定为2^x||3^y||5^z,
            如果将每次当前丑数都分别乘以2，3，5则较小的丑数在多次乘以丑数因子后会与较大的丑数重复，
            故我们每次将分别乘以2，3，5所得的丑数中去最小值加入到丑数链表中，

 **/
package CodingTest;

import java.util.*;
public class unglyNumber {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        //add进第一个丑数1
        list.add(1);
        //三个下标用于记录丑数的位置
        int i2 = 0,i3 = 0,i5 = 0;
        while(list.size()<index){
            //三个数都是可能的丑数，去最小的放进丑数数组里
            int n2 = list.get(i2)*2;
            int n3 = list.get(i3)*3;
            int n5 = list.get(i5)*5;
            int min = Math.min(n2,Math.min(n3,n5));
            list.add(min);
            if(min == n2)
                i2++;
            if(min == n3)
                i3 ++;
            if(min == n5)
                i5++;
        }
        return list.get(list.size()-1);
    }
}

